<?php
/*
 * 子数组的最大累加和问题
 * 【题目】
 * 给定一个数组arr，返回子数组的最大累加和。
 * 例如，arr=[1,-2,3,5,-2,6,-1]，
 * 所有的子数组中，[3,5,-2,6]
 * 可以累加出最大的和12，所以返回12。
 * 【要求】
 * 如果arr长度为N，要求时间复杂度为O(N)，额外空间复杂度为O(1)。
 * 【补充题目】
 * 给定一个数组arr，返回两个不相容子数组的最大累加和。
 */

$arr = [1,-2,3,5,-2,6,-1];
$obj = new Code_01_MaxSubArraySum();
$obj->main($arr);

class Code_01_MaxSubArraySum
{
    /*
     * 设arr的长度为N，假设其中有一段【L，R】的子数组，符合子数组和最大且是这个和中长度最长的。
     * 1、以L-1作为后缀的任意一段的累加和肯定是负数（如果是正数就与【L，R】是子数组和最大的假设矛盾了）
     * 2、【L，R】之间的一点Z，肯定符合L+Z>=0（如果是负数也同样与假设矛盾）
     * cur实际表示的是从某一个key开头往下加，到L-1肯定跳到了0，到L就变成了0+arr[L]
     */
    public function main($arr)
    {
        $max = PHP_INT_MIN;
        $cur = 0;
        foreach ($arr as $val) {
            $cur += $val;
            $max = max($max, $cur);
            if ($cur < 0) {
                $cur = 0;
            }
        }
        echo $max;
        return $max;
    }
}